package com.eatme.leetcode.problems;
/**
 * 307. 区域和检索 - 数组可修改 - range-sum-query-mutable
 */
public class NumArray307V1 {
    private int[] sum;  // sum[i] 存储前i个元素和,sum[0] = 0
    // sum[i] 存储nums[0...i-]的和
    private int[] data;

    // 超时解答
    public NumArray307V1(int[] nums) {
        data = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            data[i] =nums[i];
        }
        sum = new int[nums.length+1];
        sum[0] = 0;
        for (int i = 1; i < sum.length; i++)
            sum[i] = sum[i-1]+nums[i-1];
    }

    public void update(int index, int val) {
        data[index] =val;
        for (int i = index+1; i < sum.length; i++)
            sum[i] = sum[i-1] +data[i-1];
    }

    public int sumRange(int i,int j) {
        return  sum[j+1] -sum[i];
    }

    public static void main(String[] args) {

        NumArray307V1 numArray = new NumArray307V1(new int[]{1, 3, 5});
        System.out.println(numArray.sumRange(0, 2));; // 返回 1 + 3 + 5 = 9
        numArray.update(1, 2);   // nums = [1,2,5]
        System.out.println(numArray.sumRange(0, 2)); // 返回 1 + 2 + 5 = 8
    }
}
